﻿#include <iostream>

static int howManyBracketsNeeded(const char* text)
{
    int countNeeded = 0;
    int count = 0;
    int index = 0;
    int len = strlen(text);
    while (index < len)
    {
        char cur = text[index++];
        if (cur == '(') ++count;
        else --count;

        if (count < 0)
        {
            count = 0;
            ++countNeeded;
        }
    }

    countNeeded += count;
    return countNeeded;
}

// 一个完整的括号字符串定义规则如下:
// 1. 空字符串是完整的。
// 2. 如果s是完整的字符串，那么"(s)"也是完整的。
// 3. 如果s和t是完整的字符串，将它们连接起来形成的"st"也是完整的。
// 例如，"(()())", ""和"(())()"是完整的括号字符串，"())(", "()("和")"是不完整的括号字符串。
// 牛牛有一个括号字符串s，现在需要在其中任意位置尽量少得添加括号，将其转化为一个完整的括号字符串。
// 请问牛牛至少需要添加多少个括号 ?
//
//沿用判断括号是否完整的思路，使用一个count变量遍历字符串的每一个字符，如果出现count < 0，说明需要补'(';
//遍历结束后，count > 0就再补count个')'
int main_AddBracketToIntegrity()
{
    char text[256] = "((()";
    int needed = howManyBracketsNeeded(text);
    printf("%d\n", needed);
    return 0;
}